/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2025-02-05
 * Time: 21:55
 */
public class Test {
    //二叉树遍历
    public static int i = 0;
    public static BinaryTree.TreeNode createTree(String str){
        BinaryTree.TreeNode root = null;
        if (str.charAt(i) != '#'){
            root = new BinaryTree.TreeNode(str.charAt(i));
            i++;
            root.left = createTree(str);
            root.right = createTree(str);
        }else {
            i++;
        }
        return root;
    }


    //另一个树的子树
    //时间复杂度O（t*s）
    public boolean isSubtree(BinaryTree.TreeNode root, BinaryTree.TreeNode subRoot){
        if (root == null){
            return false;
        }
        if (isSameTree(root,subRoot)){
            return true;
        }
        if (isSubtree(root.left,subRoot)){
            return true;
        }
        if (isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }


    //判断两棵树是否相同
    //时间复杂度 O(min(m,n))
    public boolean isSameTree(BinaryTree.TreeNode p, BinaryTree.TreeNode q){
        if ((p == null && q != null)||(p != null && q == null)){
            return false;
        }
        //上述if没有生效，要么两个都是空要么两个都不为空
        if (p == null && q == null){
            return true;
        }
        //走完第二个if，那么p和q都不为空了
        if(p.val != q.val){
            return false;
        }
        //上述if执行完毕后，p != null && q != null && p.val == q.val
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode root = binaryTree.createTree();

        binaryTree.preOrder(root);
        System.out.println("=====");
        binaryTree.preOrderNor(root);
        System.out.println("=====");

        binaryTree.inOrder(root);
        System.out.println("=====");
        binaryTree.inOrderNor(root);
        System.out.println("=====");

        binaryTree.postOrder(root);
        System.out.println("=====");
        binaryTree.postOrderNor(root);
        System.out.println("=====");

        System.out.println("节点个数");
        binaryTree.nodeSize(root);
        System.out.println(binaryTree.countNode);

        int leafSize = binaryTree.getLeafNodeCount(root);
        System.out.println(leafSize);

        int kLeveNodeSize = binaryTree.getKLeveNodeSize(root,3);
        System.out.println(kLeveNodeSize);
    }
}
